Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
Identifieur interne : 000201 ( Main/Exploration ); précédent : 000200; suivant : 000202Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
Auteurs : David Cattanéo [France] ; Simon Perdrix [France]Source :
Abstract
The local minimum degree of a graph is the minimum degree that can be reached by means of local complementation. For any n, there exist graphs of order n which have a local minimum degree at least 0.189n, or at least 0.110n when restricted to bipartite graphs. Regarding the upper bound, we show that for any graph of order n, its local minimum degree is at most 3n/8+o(n) and n/4+o(n) for bipartite graphs, improving the known n/2 upper bound. We also prove that the local minimum degree is smaller than half of the vertex cover number (up to a logarithmic term). The local minimum degree problem is NP-Complete and hard to approximate. We show that this problem, even when restricted to bipartite graphs, is in W[2] and FPT-equivalent to the EvenSet problem, which W[1]-hardness is a long standing open question. Finally, we show that the local minimum degree is computed by a O*(1.938^n)-algorithm, and a O*(1.466^n)-algorithm for the bipartite graphs.
Url:
DOI: 10.1007/978-3-662-48971-0_23
Affiliations:
- France
- Auvergne-Rhône-Alpes, Rhône-Alpes
- Grenoble
- Université Joseph Fourier, Université Pierre-Mendès-France, Université de Grenoble
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 003196
- to stream Hal, to step Curation: 003196
- to stream Hal, to step Checkpoint: 000172
- to stream Main, to step Merge: 000201
- to stream Main, to step Curation: 000201
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms</title>
<author><name sortKey="Cattaneo, David" sort="Cattaneo, David" uniqKey="Cattaneo D" first="David" last="Cattanéo">David Cattanéo</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389148" status="INCOMING"><orgName>CAPP</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-24471" type="direct"></relation>
<relation active="#struct-3886" type="indirect"></relation>
<relation active="#struct-51016" type="indirect"></relation>
<relation active="#struct-300275" type="indirect"></relation>
<relation name="UMR5217" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-24471" type="direct"><org type="laboratory" xml:id="struct-24471" status="VALID"><orgName>Laboratoire d'Informatique de Grenoble</orgName>
<orgName type="acronym">LIG</orgName>
<desc><address><addrLine>UMR 5217 - Laboratoire LIG - 38041 Grenoble cedex 9 - France Tél. : +33 (0)4 76 51 43 61 - Fax : +33 (0)4 76 51 49 85</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.liglab.fr/</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300275" type="direct"></relation>
<relation name="UMR5217" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300275" type="indirect"><org type="institution" xml:id="struct-300275" status="VALID"><orgName>Institut National Polytechnique de Grenoble (INPG)</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5217" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01132843</idno>
<idno type="halId">hal-01132843</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01132843</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01132843</idno>
<idno type="doi">10.1007/978-3-662-48971-0_23</idno>
<date when="2015-12-09">2015-12-09</date>
<idno type="wicri:Area/Hal/Corpus">003196</idno>
<idno type="wicri:Area/Hal/Curation">003196</idno>
<idno type="wicri:Area/Hal/Checkpoint">000172</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000172</idno>
<idno type="wicri:Area/Main/Merge">000201</idno>
<idno type="wicri:Area/Main/Curation">000201</idno>
<idno type="wicri:Area/Main/Exploration">000201</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms</title>
<author><name sortKey="Cattaneo, David" sort="Cattaneo, David" uniqKey="Cattaneo D" first="David" last="Cattanéo">David Cattanéo</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389148" status="INCOMING"><orgName>CAPP</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-24471" type="direct"></relation>
<relation active="#struct-3886" type="indirect"></relation>
<relation active="#struct-51016" type="indirect"></relation>
<relation active="#struct-300275" type="indirect"></relation>
<relation name="UMR5217" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-24471" type="direct"><org type="laboratory" xml:id="struct-24471" status="VALID"><orgName>Laboratoire d'Informatique de Grenoble</orgName>
<orgName type="acronym">LIG</orgName>
<desc><address><addrLine>UMR 5217 - Laboratoire LIG - 38041 Grenoble cedex 9 - France Tél. : +33 (0)4 76 51 43 61 - Fax : +33 (0)4 76 51 49 85</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.liglab.fr/</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300275" type="direct"></relation>
<relation name="UMR5217" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300275" type="indirect"><org type="institution" xml:id="struct-300275" status="VALID"><orgName>Institut National Polytechnique de Grenoble (INPG)</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5217" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/978-3-662-48971-0_23</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The local minimum degree of a graph is the minimum degree that can be reached by means of local complementation. For any n, there exist graphs of order n which have a local minimum degree at least 0.189n, or at least 0.110n when restricted to bipartite graphs. Regarding the upper bound, we show that for any graph of order n, its local minimum degree is at most 3n/8+o(n) and n/4+o(n) for bipartite graphs, improving the known n/2 upper bound. We also prove that the local minimum degree is smaller than half of the vertex cover number (up to a logarithmic term). The local minimum degree problem is NP-Complete and hard to approximate. We show that this problem, even when restricted to bipartite graphs, is in W[2] and FPT-equivalent to the EvenSet problem, which W[1]-hardness is a long standing open question. Finally, we show that the local minimum degree is computed by a O*(1.938^n)-algorithm, and a O*(1.466^n)-algorithm for the bipartite graphs.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Auvergne-Rhône-Alpes</li>
<li>Rhône-Alpes</li>
</region>
<settlement><li>Grenoble</li>
</settlement>
<orgName><li>Université Joseph Fourier</li>
<li>Université Pierre-Mendès-France</li>
<li>Université de Grenoble</li>
</orgName>
</list>
<tree><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Cattaneo, David" sort="Cattaneo, David" uniqKey="Cattaneo D" first="David" last="Cattanéo">David Cattanéo</name>
</region>
<name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000201 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000201 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= Hal:hal-01132843 |texte= Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms }}
This area was generated with Dilib version V0.6.33. |